// [790]多米诺和托米诺平铺
struct Solution;

//leetcode submit region begin(Prohibit modification and deletion)
impl Solution {
    pub fn num_tilings(n: i32) -> i32 {
        if n <= 2 {
            return n;
        }
        const MOD: i64 = 10_i64.pow(9) + 7;
        let mut vec = vec![0;(n+1) as usize];
        vec[0] = 1;
        vec[1] = 1;
        vec[2] = 2;
        for i in 3..=n {
            let i = i as usize;
            vec[i] = (vec[i-1] * 2 + vec[i - 3]) % MOD;
        }
        vec[n as usize] as _
    }
}
//leetcode submit region end(Prohibit modification and deletion)

/// 总结：查找规律，然后推导出转移方程

#[test]
fn main() {
    assert_eq!(Solution::num_tilings(3), 5);
    assert_eq!(Solution::num_tilings(1), 1);
}